/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */

//暴力法
var getIntersectionNode = function (headA, headB) {
  let temp = headB;
  for (let i = headA; i != null; i = i.next) {
    for (let j = temp; j != null; j = j.next) {
      if (i === j) {
        return i;
      }
    }
  }
};

//哈希表法
var getIntersectionNode = function (headA, headB) {
  let temp = headB;
  const set = new Set();
  for (let i = headA; i != null; i = i.next) {
    set.add(i);
  }

  for (let j = temp; j != null; j = j.next) {
    if (set.has(j)) {
      return j;
    }
  }
};

// 双指针法
// a 走完走b   b 走完走a
var getIntersectionNode = function (headA, headB) {
  let a = headA,
    b = headB;
  while (a != b) {
    a = a != null ? a.next : headB;
    b = b != null ? b.next : headA;
  }
  return a;
};
